package leetcode_800;

/**
 *@author 周杨
 *MinimumASCIIDeleteSumForTwoStrings_712_ 给定两个字符串 要求在删掉ASC码最低的字符情况下 使两者相等
 *describe: 其实也和求公共子串没有太大差别 用动态规划 AC 70%
 *2018年10月11日 下午12:08:06
 */
public class MinimumASCIIDeleteSumForTwoStrings_712_ {
	public int minimumDeleteSum(String s1, String s2) {
		int dp[][]=new int[s1.length()+1][s2.length()+1];
        char chars1[]=s1.toCharArray();
        char chars2[]=s2.toCharArray();
        //初始化循环条件 如果一个都不匹配 其实只删除了其中一个字符串
        for(int i=1;i<=s1.length();++i) {
        	dp[i][0]=dp[i-1][0]+chars1[i-1];
        }
        for(int i=1;i<=s2.length();++i) {
        	dp[0][i]=dp[0][i-1]+chars2[i-1];
        }
        
        for(int i=1;i<=s1.length();++i) {
        	for(int j=1;j<=s2.length();++j) {
        		if(chars1[i-1]!=chars2[j-1]) {//没有匹配上 那么考虑删除字符
        			dp[i][j]+=Math.min(dp[i-1][j]+chars1[i-1]
        					, dp[i][j-1]+chars2[j-1]);
        		}
        		else {//相等了 那么不必删除
        			dp[i][j]=dp[i-1][j-1];
        		}
        	}
        }
        return dp[s1.length()][s2.length()];
    }
}
